#include<iostream>
#include<string>
#include<vector>

using namespace std;

bool isValid(int x, int y, char k, vector<string>& board) {
    for (int i = 0; i < y; ++i) {
        if (board[x][i] == k) return false;
    }
    for (int i = y + 1; i < 9; ++i) {
        if (board[x][i] == k) return false;
    }
    for (int i = 0; i < x; ++i) {
        if (board[i][y] == k) return false;
    }
    for (int i = x + 1; i < 9; ++i) {
        if (board[i][y] == k) return false;
    }
    for (int i = x / 3 * 3; i <= x / 3 * 3 + 2; ++i) {
        for (int j = y / 3 * 3; j <= y / 3 * 3 + 2; ++j) {
            if (board[i][j] == k) return false;
        }
    }
    return true;
}
bool bt(vector<string>& board) {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
                for (char k = '1'; k <= '9'; ++k) {
                    if (isValid(i, j, k, board)) {
                        board[i][j] = k;
                        if (bt(board)) return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
    }
    return true;
}
void solveSudoku(vector<string>& board) {
    if (bt(board)) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                cout << board[i][j];
                if (j == 2 || j == 5) cout << "  ";
            }
            if (i == 2 || i == 5) cout << endl;
            cout << endl;
        }
    }
    else {
        printf("此数独无解！！！");
    }
}

int main() {
    cout << "-----9*9 数独破解器-----" << endl;
    cout << "输入要求：" << endl << "1. 空白地方用'.'号代替（忽略引号）" << endl << "2. 不空格的连续输入九个数，然后回车，重复此操作" << endl;
    cout << endl << endl << "↓开始输入↓" << endl;
    vector<string> board(9);
    for (int i = 0; i < 9; ++i) {
        cin >> board[i];
    }
    solveSudoku(board);
    return 0;
}